File::Fu has another version out, now with which() support. I looked at possibly replacing File::Which entirely, but unfortunately only had the time to just wrap it. In this case, it's not as painful as wrapping File::Temp, but that sort of choice is an ongoing struggle in the land of revisiting API designs for "good enough" and "what we have works" code.
And it now has a bug report, but Win32 support is on the back burner mostly for lack of a convenient mechanism for testing on that platform (though I honestly haven't had much chance to juggle the trade-offs of how it would be best implemented.) If you're interested, please feel free to take a run at it.